﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
namespace hash_bucket
{
	template<class V>
	struct HashNode//前置声明
	{
		V _data;
		HashNode<V>* _next;
		HashNode(const V& data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};
	// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	/*template<class K, class V, class KeyOfT, class HF>
	class HashBucket;*/
	template<class K, class V, class KeyOfT, class Hash>//前置声明
	class HashTable;
	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	template <class K, class V, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HBIterator
	{
		typedef HashTable<K, V, KeyOfT, Hash> HashTable;
		typedef HashNode<V>* PNode;
		typedef HBIterator<K, V, Ptr, Ref, KeyOfT, Hash> Self;

		HBIterator(PNode pNode = nullptr, HashTable* pHt = nullptr)
			:_Node(pNode)
			, _Ht(pHt)
		{}
		Self& operator++()
		{
			//if (_Node->_next)
			//{
			//	// 当前桶还有节点
			//	_Node = _Node->_next;
			//}
			//else
			//{
			//	// 当前桶走完了，找下一个不为空的桶
			//	KeyOfT kot;
			//	Hash hs;
			//	size_t hashi = hs(kot(_Node->_data)) % _Ht->_tables.size();
			//	++hashi;
			//	while (hashi < _Ht->_tables.size())
			//	{
			//		if (_Ht->_tables[hashi])
			//		{
			//			break;
			//		}
			//		++hashi;
			//	}
			//	if (hashi == _Ht->_tables.size())
			//	{
			//		_Node = nullptr; // end()
			//	}
			//	else
			//	{
			//		_Node = _Ht->_tables[hashi];
			//	}
			//}
			//return *this;//正确答案

					//	// 当前迭代器所指节点后还有节点时直接取其下一个节点
		//	//if (_Node->_next)
		//	//	_Node = _Node->_next;
		//	//else
		//	//{
		//	//	KeyOfT kot;
		//	//	Hash hot;
		//	//	size_t hashi = hot(kot(_Node->_data)) % _Ht->_tables.size();
		//	//	size_t old_hashi = hashi;
		//	//	++hashi;
		//	//	// 找下一个不空的桶，返回该桶中第一个节点
		//	//		while (_Ht->_tables[hashi] == nullptr)
		//	//		{
		//	//			++hashi %= _Ht->_tables.size();
		//	//			if (hashi == old_hashi)
		//	//			{
		//	//				_Node = nullptr;
		//	//				break;
		//	//			}
		//	//			else
		//	//			{
		//	//				_Node = _Ht->_tables[hashi];
		//	//				break;
		//	//			}
		//	//		}
		//	//}
		//	//return *this;//我写的

			if (_Node->_next)
				_Node = _Node->_next;
			else
			{
				KeyOfT kot;
				Hash hot;
				size_t hashi = hot(kot(_Node->_data)) % _Ht->_tables.size();
				++hashi;
				while (hashi < _Ht->_tables.size())
				{
					if (_Ht->_tables[hashi])
					{
						break;
					}
					++hashi;
				}
				//if (_Node == _Ht->_tables[hashi])
				if (hashi == _Ht->_tables.size())

					_Node = nullptr;
				else
					_Node = _Ht->_tables[hashi];

			}
			return *this;

		}
		//}
		Self operator++(int)
		{
			PNode tmp = *this;
			++(*this);
			return tmp;
		}
		Ref operator*()
		{
			return (_Node->_data);
		}
		Ptr operator->()
		{
			return &(_Node->_data);
		}
		bool operator==(const Self& it) const
		{
			return _Node == it._Node;
		}
		bool operator!=(const Self& it) const
		{
			return _Node != it._Node;
		}

		PNode _Node;             // 当前迭代器关联的节点
		HashTable* _Ht;         // 哈希桶--主要是为了找下一个空桶时候方便
	};

	template<class K, class V, class KeyOfT, class Hash>
	class HashTable
	{
	public:
		typedef HashNode<V> Node;
		typedef HBIterator<K, V, V*, V&, KeyOfT, Hash> Iterator;
		typedef HBIterator<K, V, const V*, const V&, KeyOfT, Hash> const_Iterator;
		template <class K, class V, class Ptr, class Ref, class KeyOfT, class Hash>//友元
		friend struct HBIterator;
	public:
		Iterator Begin()
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}
			return End();
		}
		const_Iterator Begin()const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return const_Iterator(cur, this);
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr,this);
		}
		const_Iterator End()const
		{
			return const_Iterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];

				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_n = 0;
		}

		pair<Iterator, bool> Insert(const V& data)
		{
			Hash hs;
			KeyOfT kot;
			Iterator it = Find(kot(data));
			if (it == nullptr)
			{
				if (_n == _tables.size())
				{
					vector<Node*> newtables(_tables.size() * 2, nullptr);
					for (size_t i = 0; i < _tables.size(); i++)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;
							size_t hashi = hs(kot(cur->_data)) % newtables.size();
							cur->_next = newtables[hashi];
							newtables[hashi] = cur;
							cur = next;
						}
						_tables[i] = nullptr;
					}
					_tables.swap(newtables);
				}
				size_t hashi = hs(kot(data)) % _tables.size();
				Node* newnode = new Node(data);
				newnode->_next = _tables[hashi];
				_tables[hashi] = newnode;
				++_n;
				return make_pair(Iterator(newnode,this), true);
			}
			else
				return make_pair(Iterator(it), false);
		}

		Node* Find(const K& key)
		{
			Hash hot;
			KeyOfT kot;
			size_t hashi = hot(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Hash hot;
			KeyOfT kot;
			size_t hashi = hot(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (cur == _tables[hashi])
						_tables[hashi] = cur->_next;
					else
						prev->_next = cur->_next;
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
			
		}

		size_t Size() const
		{
			return _n;
		}
		bool Empty() const
		{
			return (_n == 0);
		}
	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};

}